package com.xiaoyu.string;

/**
 * @program: DS_and_A
 * @description:
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * @author: YuWenYi
 * @create: 2021-04-24 09:49
 **/
public class LongestCommonPrefix {
/*   个人解法: 先拿到第一个字符串的第一个字母作为首前缀,然后与判断其他的字符串是否包含这个前缀,
     如果全部包含,就让前缀在原来的基础上加一个
     如果有一个不包含,说明新加的那个前缀是无效前缀,取消舍去然后返回上一步的前缀


    */

    //首先不能让字符串数组为空,或者首个字母为""
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null ||strs.length == 0 ||"".equals(strs[0]) )  //不能让首个字母为"",否则会在prefix.substring(0,prefix.length()-1);报错
            return "";
        String prefix = "";
        int len = 1;
        while (true){
            prefix = strs[0].substring(0,len);
            for (int j = 1; j < strs.length; j++) {
                if (!strs[j].startsWith(prefix)) {
                    return prefix.substring(0, prefix.length() - 1);  //进入到这里了,说明上一步新加的前缀是无效的,需要舍弃
                }
            }
            len++;
            if (len > strs[0].length()){    //如果不加这个,那么如果是"flower","flower"的情况,将会出现i++到7导致数组越界
                break;
            }
        }
        return prefix;
    }

    //大佬解法!纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，
    //如果相同则继续对下一列进行比较，
    //如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
    //一次只比较一个字符,效率更高
    /*public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }*/


    public static void main(String[] args) {
        String[] strs = new String[]{"flower","flower","flower"};   //fl

        String prefix = longestCommonPrefix(strs);
        System.out.println("前缀为:"+prefix);
    }

}
